package leetcode_字符串._02回文串;

import java.util.ArrayList;

/**
 * 验证回文串
 * 给定的字符串去掉除了字母和数字组成的字符串是否是回文串
 * 算法 : 使用双指针算法
 * 先排除空串 , 如果是空字符串 , 直接返回 true   s.trim().length() == 0
 * 先把字符串中的除字母和数字之外的字符给去掉 , 然后再判断
 * 使用左右指针 , 判断指针指向的字符是否相等
 */
public class _125 {
    public static void main(String[] args) {
        System.out.println(isPalindrome_perfect(".,"));
    }

    public static boolean isPalindrome(String s) {
        if (s.trim().length() == 0) {
            return true;
        }
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z' || s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                list.add(s.charAt(i));
            } else if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                list.add((char) ('A' + (s.charAt(i) - 'a')));
            }
        }
        // 字符串中没有字母和数字
        if (list.size() == 0) {
            return true;
        }
        int l = 0, r = list.size() - 1;
        while (list.get(l) == list.get(r) && l < r) {
            ++l;
            --r;
        }
        return l >= r;
    }

    /**
     * 用 stringBuffer 存储字符串 , 直接只用该类的 reverse() 方法 , 判断翻转后的字符串与翻转前的字符串是否相同
     *
     * @param s
     * @return
     */
    public static boolean isPalindrome_tow(String s) {
        if (s.trim().length() == 0) {
            return true;
        }
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if (Character.isLetterOrDigit(s.charAt(i))) {
                buffer.append(Character.toUpperCase(s.charAt(i)));
            }
        }
        StringBuffer reverse = new StringBuffer(buffer).reverse();
        return buffer.toString().equals(reverse.toString());
    }

    /**
     * 不进行筛选
     * 直接用双指针
     */
    public static boolean isPalindrome_perfect(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < s.length() && !Character.isLetterOrDigit(s.charAt(l))) {
                ++l;
            }
            while (r >= 0 && !Character.isLetterOrDigit(s.charAt(r))) {
                --r;
            }
            if (l >= r) {
                break;
            }
            if (Character.toUpperCase(s.charAt(l)) != Character.toUpperCase(s.charAt(r))) {
                break;
            }
            ++l;
            --r;
        }
        return l >= r;
    }
}
